package com.mlamp.回溯;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

public class 串联字符串的最大长度 {

    private List<String> res = new ArrayList<>();
    private int maxLength = Integer.MIN_VALUE;

    public static void main(String[] args) {
        串联字符串的最大长度 instance = new 串联字符串的最大长度();
        List<String> input = Arrays.asList("un", "iq", "ue");
        input = Arrays.asList("cha", "r", "act", "ers");
        input = Arrays.asList("abcdefghijklmnopqrstuvwxyz");
        input = Arrays.asList("a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "n", "o", "p");
        int i = instance.maxLength(input);
        System.out.println(i);

    }


    public int maxLength(List<String> arr) {
        LinkedList<String> trace = new LinkedList<>();
        core(arr, trace);
        return this.maxLength;
    }

    public void core(List<String> arr, LinkedList<String> trace) {
        maxLength = Math.max(maxLength, trace.stream().map(item -> item.length()).reduce((i, j) -> i + j).orElseGet(() -> 0));
        for (String item : arr) {
            if (contains(trace, item)) continue;
            trace.add(item);
            core(arr, trace);
            trace.removeLast();
        }
    }

    public boolean contains(LinkedList<String> trace, String input) {
        if (trace.isEmpty()) return false;
        char[] chars = input.toCharArray();
        for (String item : trace) {
            for (int i = 0; i < chars.length; i++) {
                if (item.indexOf((int) (chars[i])) != -1) return true;
            }
        }
        return false;
    }


}
